【题解】 [HNOI2008]玩具装箱TOY 斜率优化DP luoguP3195 | Qiuly's blog!

【题解】 [HNOI2008]玩具装箱TOY 斜率优化DP luoguP3195

Posted on | Edited on | In | Comments:

差不多搞懂了斜率优化吧……说实话网上的文章都写得很迷，还好找到了一个不错的文章：转送门戳我(￣▽￣)~* 。(为什么突然发现这道题和诗人小G很像呢)

这个 $\texttt{DP}$ 方程谁都会设：设 $f_i$ 表示前 $i$ 个玩具的最小费用，转移显然如下：

(其中 $sum$ 是前缀和)。这个复杂度是 $O(n^2)$ 的，过不去……

继续推式子：

设 $s_i=sum_i+i$ ，我们假设 $j$ 为最优决策，将 $\min$ 去掉。

于是上面的式子变成了 $y=kx+b$ 的形式，其中 $y=f_j+s_i^2+(s_j+l)^2$ ，$k=2\cdot s_i$ ，$x=s_j+l$ ，$b=f_i$ 。

然后将 $x,y$ 两个值作为点 $(x,y)$ 放到平面上即可，因为最终答案是取 $min$ ，所以我们需要维护的是下凸壳。有一点需要注意的是，我们算斜率的时候可以将每个点的常数项或者只和 $i$ 有关的项去掉，因为算斜率是相减的，减的时候这些项同样也没了。

上面的 $x$ 中的 $l$ 是常数项于是可以省略，$y$ 中的 $s_i^2$ 只和 $i$ 有关，于是也省略掉。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <iostream>
#define S(x) ((x)*(x))
using namespace std;
const int N=1e5+2;
int n,l,head,tail;
long long f[N],s[N],q[N];
double X(int i) {return s[i];}/*每个点的x坐标*/
double Y(int i) {return f[i]+S(s[i]+l);}/*每个点的y坐标*/
double slope(int i,int j) {return (Y(j)-Y(i))/(X(j)-X(i));}/*算斜率*/
int main() {
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;++i) scanf("%lld",&s[i]),s[i]+=s[i-1];
    for(int i=1;i<=n;++i) s[i]+=i;
    for(int i=1;i<=n;++i) {
        while(head<tail&&slope(q[head],q[head+1])<2*s[i]) ++head;
        f[i]=f[q[head]]+S(s[i]-s[q[head]]-l-1);/*转移*/
        while(head<tail&&slope(q[tail],i)<slope(q[tail],q[tail-1])) --tail;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

下面来解释一些问题。

1.为什么要维护下凸壳

因为我们的 $\texttt{DP}$ 方程是在取 $\min$ ，如果是 $\max$ 的话则维护上凸壳。而且维护下凸壳显然是让 $f_i$ 更小。

以上面为例，我们用 $y=kx+b​$ 的直线从下面网上扫，注意这条直线的斜率就是 $k​$ 。很显然如果我们从下往上这样扫越往上扫 $b​$ 越大(不明白的画画图)，但是我们的目的是使得 $b​$ 最小( $b​$ 就是 $f_i​$ ) 。下凸壳包含了最下面的所有点，显然不是下凸壳上的点一定不能成为最优的。

2.维护队列的过程是什么鬼操作

首先第一个过程，也就是下面的代码：

1
while(head<tail&&slope(q[head],q[head+1])<2*s[i]) ++head;

上面讲了我们需要使得 $b​$ 最小，那么最优的决策点在直线从下往上扫的过程中肯定是最先扫到的，因为那样可以保证 $f_i​$ 最小。假设最优的点为 $i​$ ，上一个点为 $j​$ ，下一个点为 $k​$ ，那么 $i​$ 一定保证 $j​$ 到 $i​$ 的斜率小于直线斜率并且 $i​$ 到 $k​$ 的斜率大于直线斜率。

然后我们会发现对于单调上增的需要更新的 $i​$ ，其直线的斜率 $k​$ 一定是单调上增的，因为前缀和是单调上增的。

所以对于斜率已经不满足要求的点直接踢出队就好了。

然后康康出队的过程。如果在纸上画画会发现，如果满足 slope(q[tail],i)<slope(q[tail],q[tail-1]) ，那么说明 $q[tail]$ 已经不再下凸壳中了！没错吧？那么这个时候 $q[tail]$ 永远也不可能成为最优的转移点了，直接丢掉即可。

最后有一些斜率优化的套路总结(自己总结出来的)：

  • $\texttt{DP}$ 方程取 $\min$ 就维护下凸壳，取 $\max$ 就维护上凸壳
  • $y=kx+b​$ 中的 $k​$ 一定要是常量或者是完全是 $i​$ 的量(例如 $s_i,2\cdot g_i^2​$ 等)，$b​$ 一定是你需要转移的对象(就是 $f_i​$ )，$x​$ 和 $y​$ 两个值一定要包含和 $j​$ 有关的值，要随 $j​$ 的变化而变化。
  • 提炼出来的 $x,y$ 放到坐标系上之前记得去掉没用的值。

差不多就这些吧，也不知道是不是完全正确，至少这个套路还是过了几道题目的。

本文标题:【题解】 [HNOI2008]玩具装箱TOY 斜率优化DP luoguP3195

文章作者:Qiuly

发布时间:2019年04月24日 - 00:00

最后更新:2019年04月28日 - 13:51

原始链接:http://qiulyblog.github.io/2019/04/24/[题解]luoguP3195/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。